#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <tr1/unordered_map>

#include <ctime>
#include <sys/time.h>

/* tokyocabinet library */
#include <tcutil.h>
#include <tchdb.h>
#include <tcbdb.h>
#include <tcfdb.h>
#include <tcadb.h>

namespace pocketj {

  typedef std::tr1::unordered_map
  <int, std::vector<std::tr1::unordered_map<int, int > > > Index;

  const std::string MAX_WORD_ID = "MAX_WORD_ID";

  namespace util {

    std::vector<std::string> split(std::string str, std::string delim)
    {
      std::vector<std::string> result;
      uint64_t cutAt;
      while((cutAt = str.find_first_of(delim)) != str.npos){
        if(cutAt > 0) result.push_back(str.substr(0, cutAt));
        str = str.substr(cutAt + 1);
      }
      if(str.length() > 0) result.push_back(str);
      return result;
    }

    void ucsToUtf(uint16_t c, int num, std::string& result) {
      uint16_t buf[num];
      buf[0] = c;
      const uint16_t* ary = buf;
      char rv[4];
      tcstrucstoutf(ary, 1, rv);
      result = rv;
    }

    void getNgram(std::vector<std::string>& ngram, std::string doc, unsigned int num)
    {
      std::deque<std::string> queue(0);
      std::deque<std::string>::iterator itr;
      int anum;
      uint16_t stack[66563];
      uint16_t* ary = stack;
      tcstrutftoucs(doc.c_str(), ary, &anum);
      for (int i = 0; i < anum ; i++) {
        uint16_t cBuf = ary[i];
        std::string c;
        pocketj::util::ucsToUtf(cBuf, 1, c);
        if (queue.size() < num) {
          queue.push_back(c);
        } else {
          std::string token;
          itr = queue.begin();
          while (itr != queue.end()) {
            token += *itr;
            itr++;
          }
          queue.pop_front();
          queue.push_back(c);
          ngram.push_back(token);
        }
      }
    }

    void getNgram2(std::vector<std::string>& ngram, std::string doc, unsigned int num)
    {
      int anum;
      uint16_t stack[66563];
      uint16_t* ary = stack;
      tcstrutftoucs(doc.c_str(), ary, &anum);
      unsigned int cnt = 0;
      std::string token;
      for (int i = 0; i < anum ; i++) {
        uint16_t cBuf = ary[i];
        std::string c;
        pocketj::util::ucsToUtf(cBuf, 1, c);
        if (cnt < num) {
          token += c;
          cnt++;
        } else {
          ngram.push_back(token);
          token = c;
          cnt   = 1;
        }
      }
      ngram.push_back(token);
    }

    int createRandomInt(int max) {
      int rv = static_cast<int>(std::rand() % max);
      return rv;
    }

    std::string createRandomString() {
      std::string rv;
      int wd;
      int num = createRandomInt(100);
      for(int i = 0; i < num; i++){
        wd = std::rand() % 26 + 97;
        char wdbuf = static_cast<char>(wd);
        rv = rv + wdbuf;
      }
      return rv;
    }
  }

  class Feature {
    friend class LessAn;
  public:
    Feature(){}

    Feature(int id, int df)
    {
      this->id = id;
      this->df = df;
    }

    ~Feature(){}

    void setID(int id)
    {
      this->id = id;
    }

    void setDF(int df)
    {
      this->df = df;
    }

    int getID()
    {
      return id;
    }

    int getDF()
    {
      return df;
    }

  private:
    int id;
    int df;
  };

  class Doc {

  public:
    Doc()
    {
      featureNum = 0;
    }

    ~Doc() {}

    void setFeatureNum(int featureNum)
    {
      this->featureNum = featureNum;
    }

    void setFeature(const std::vector<Feature>& features)
    {
      this->features = features;
    }

    int getFeatureNum()
    {
      return featureNum;
    }

    void itrInit()
    {
      itr = features.begin();
    }

    bool getNextFeature(int& id, int& df)
    {
      if (itr == features.end()) return false;
      Feature feature = *itr;
      id = feature.getID();
      df = feature.getDF();
      itr++;

      return true;
    }

    bool getFeature(int index, int& id, int& df)
    {
      if (index > featureNum) return false;
      Feature feature = features[index];
      id = feature.getID();
      df = feature.getDF();
      return true;
    }

  private:
    int featureNum;
    std::vector<Feature> features;
    std::vector<Feature>::iterator itr;
  };

  class LessAn {
  public:
    bool operator() (const Feature& a, const Feature&b) {
      return a.df < b.df;
    }
  };


  class Analyzer {
    friend class POCKETJTestCase;
  public:
    Analyzer(double threshold, double param, std::string path) :
      T(threshold),
      PARAM(param), // ookikunaru hodo zatu ni naru.
      DOC_ID_KEY(1),
      WORD_ID_KEY(2),
      DOC_LENGTH_KEY(3)
    {
      openDB(path);
      index.rehash(3000000);
      index.max_load_factor(1.0);
    }

    ~Analyzer()
    {
      closeDB();
    }

    bool addDoc(int docID, std::string& strhoge)
    {
      std::string str = strhoge.substr(0, 1000);
      if (docSave.find(docID) != docSave.end()) return false;
      std::vector<std::string> ngram;
      pocketj::util::getNgram(ngram, str, 3);
      std::vector<Feature> featureList;
      std::tr1::unordered_map<std::string, int> tokenID;
      std::tr1::unordered_map<std::string, int>::iterator itr;
      Doc doc;
      unsigned int featureSiz = ngram.size();
      for (unsigned int i = 0; i < featureSiz; i++) {
        int id = 1;
        std::string token = ngram.at(i);
        if ((itr = tokenID.find(token)) != tokenID.end()) {
          id += itr->second;
        }
        tokenID.insert(std::pair<std::string, int>(token, id));
        char* idStr     = tcsprintf("%d", id);
        std::string key = token + "_" + idStr;
        free(idStr);
        char* keyID = tchdbget2(wordIdHdb, key.c_str());
        if (!keyID) {
          char* maxIDBuf = tchdbget2(wordIdHdb, pocketj::MAX_WORD_ID.c_str());
          int maxID      = std::atoi(maxIDBuf) + 1;
          free(maxIDBuf);
          keyID = tcsprintf("%d", maxID);
          tchdbput2(wordIdHdb, pocketj::MAX_WORD_ID.c_str(), keyID);
          tchdbput2(wordIdHdb, key.c_str(), keyID);
        }
        tchdbaddint(dfHdb, keyID, std::strlen(keyID), 1);
        Feature feature(std::atoi(keyID), 1);
        featureList.push_back(feature);
        free(keyID);
      }
      doc.setFeatureNum(featureSiz);
      doc.setFeature(featureList);
      docSave.insert(std::make_pair<int, Doc>(docID, doc));
      std::vector<int> docIDSiz(2);
      docIDSiz[1] = docID;
      docIDSiz[0] = featureSiz;
      queue.push(docIDSiz);

      return true;
    }

    void sortDoc()
    {
      std::map<int, Doc>::iterator itr = docSave.begin();
      std::map<int, Doc> docSaveBuf;
      while (itr != docSave.end()) {
        int docID = itr->first;
        Doc doc   = itr->second;
        std::vector<Feature> features;
        doc.itrInit();
        int id, df;
        while ((doc.getNextFeature(id, df)) != false) {
          char* idBuf = tcsprintf("%d", id);
          char* dfBuf = tchdbget2(dfHdb, idBuf);
          int df      = dfBuf ? *(int*)dfBuf : 0;
          free(dfBuf);
          free(idBuf);
            Feature feature(id, df);
            features.push_back(feature);
        }
        sort(features.begin(), features.end(), LessAn());
        doc.setFeature(features);
        itr++;
        docSave.erase(docID);
        docSave.insert(std::make_pair<int, Doc>(docID, doc));
      }
    }

    bool doJoin(std::map<int, std::set<int> >& result)
    {
      int xID;
      while((getIDFromQueue(xID)) != false) {
        std::map<int, int> A;
        Doc xDoc    = docSave[xID];
        int xLength = xDoc.getFeatureNum();
        double p    = std::ceil(xLength - (T * xLength) + 1);
        int wID, df;
        int wi = 1;
        xDoc.itrInit();
        while((xDoc.getNextFeature(wID, df)) != false) {
          Index::iterator idxItr = index.find(wID);
          if (idxItr != index.end()) {
            std::vector<std::tr1::unordered_map<int, int> > yIndex = idxItr->second;
            for (unsigned int i = 0; i < yIndex.size(); i++) {
              std::tr1::unordered_map<int, int> yMapBuf = yIndex[i];
              int yID     = yMapBuf[DOC_ID_KEY];
              int yLength = yMapBuf[DOC_LENGTH_KEY];
              int yj      = yMapBuf[WORD_ID_KEY];
              Doc yDoc    = docSave[yID];
              if (xID == yID) continue;
              if (yLength >= T * xLength) {
                double tt     = (T / (1 + T));
                int lengthh   = xLength + yLength;
                double alpha  = ( tt * lengthh);
                double ubound = getUbound(xLength, wi, yLength, yj);
                int Ay        = A[yID];
                if (Ay + ubound >= alpha) {
                  A[yID] = Ay + 1;
                } else {
                  A[yID] = 0;
                }
              }
            }
          }
          addWordToIndex(wID, xID, wi, xLength);
          wi++;
          if (wi > p) break;
        }

        //verify
        std::vector<int> relatedDocs;
        verify(A, xDoc, p, xID, relatedDocs);

        if (relatedDocs.size() > 0) {
          std::set<int> relatedIDs;
          for (unsigned int i = 0; i < relatedDocs.size(); i++) {
            relatedIDs.insert(relatedDocs[i]);
          }
          std::set<int>::iterator itr = relatedIDs.begin();
          while (itr != relatedIDs.end()) {
            int rID = *itr;
            if ((result.find(rID)) != result.end()) {
              std::set<int> relatedIDsBuf = result[rID];
              std::set<int>::iterator i;
              for(i = relatedIDsBuf.begin(); i != relatedIDsBuf.end(); i++) {
                relatedIDs.insert(*i);
              }
              result.erase(rID);
            }
            result.insert(std::make_pair<int, std::set<int> >(xID, relatedIDs));
            itr++;
          }
        }
      }

      return true;
    }


    // will be removed
    void checkQueue()
    {
      while(!queue.empty()){
        std::vector<int> buf = queue.top();
        std::cout << buf.at(0) << "\t" << buf.at(1) << std::endl;
        queue.pop();
      }
    }


    // will be removed
    void itrDfDb()
    {
      tchdbiterinit(dfHdb);
      char* key;
      while ((key = tchdbiternext2(dfHdb)) != NULL) {
        int vsiz;
        void* vbuf = tchdbget(dfHdb, key, std::strlen(key), &vsiz);
        int df     = vbuf ? *(int*)vbuf : 0;
        std::cout << key << "\t" << df << std::endl;
        std::free(vbuf);
      }
      std::cout << std::endl;
    }

    // will be removed
    void itrdocSave()
    {
      std::map<int, Doc>::iterator itr = docSave.begin();
      while(itr != docSave.end()) {
        Doc doc = itr->second;
        std::cout << doc.getFeatureNum() << std::endl;
        doc.itrInit();
        int id, df;
        while ((doc.getNextFeature(id, df)) != false) {
          std::cout << id << ":" << df << " | ";
        }
        std::cout << std::endl;

        itr++;
      }
    }

    // will be removed
    void itrIndex()
    {
      Index::iterator itr = index.begin();
      while (itr != index.end()) {
        int key = itr->first;
        //std::vector<std::map<int, int> > words = itr->second;
        std::vector<std::tr1::unordered_map<int, int> > words = itr->second;
        std::cout << key << std::endl;
        for (unsigned int i = 0; i < words.size(); i++) {
          std::tr1::unordered_map<int, int> mapBuf = words[i];
          std::tr1::unordered_map<int, int>::iterator bufItr = mapBuf.begin();
          while (bufItr != mapBuf.end()) {
            int bufKey = bufItr->first;
            int val = bufItr->second;
            std::cout << "\t" << bufKey << ":" << val << std::endl;
            bufItr++;
          }
          std::cout << "\t-------" << std::endl;
        }
        itr++;
      }
    }

  private:
    const double T;
    const int PARAM;
    const int DOC_ID_KEY;
    const int WORD_ID_KEY;
    const int DOC_LENGTH_KEY;
    TCHDB* dfHdb;
    TCHDB* wordIdHdb;
    std::priority_queue<std::vector<int> > queue;
    Index index;
    std::map<int, Doc> docSave;

    enum {
      TRUNC = HDBOWRITER|HDBOCREAT|HDBOTRUNC,
      READ  = HDBOREADER,
    };

    bool getIDFromQueue(int& docID)
    {
      int queueSiz = queue.size();
      if (queueSiz <= 0) return false;
      std::vector<int> buf = queue.top();
      docID = buf.at(1);
      queue.pop();

      return true;
    }

    double getUbound(int xLength, int xWordID, int yLength, int yWordID)
    {
      double ubound = 0;
      int xMin      = xLength - xWordID;
      int yMin      = yLength - yWordID;
      int min       = (xMin >= yMin) ? yMin : xMin;

      return ubound = PARAM + min;
    }

    void addWordToIndex(int word, int docID, int wordID, int length)
    {
      std::tr1::unordered_map<int, int> mapBuf;
      mapBuf.insert(std::make_pair<int, int>(DOC_ID_KEY, docID));
      mapBuf.insert(std::make_pair<int, int>(WORD_ID_KEY, wordID));
      mapBuf.insert(std::make_pair<int, int>(DOC_LENGTH_KEY, length));
      index[word].push_back(mapBuf);
    }

    void verify(std::map<int, int>& A,
                Doc& x, int p, int xID, std::vector<int>&  result)
    {
      std::map<int, int>::iterator itrA = A.begin();
      while(itrA != A.end()) {
        int yID  = itrA->first;
        int yVal = itrA->second;
        if (yVal > 0) {
          int px        = p;
          int xLength   = x.getFeatureNum();
          Doc y         = docSave[yID];
          int yLength   = y.getFeatureNum();
          int py        = std::ceil(yLength - (T * yLength) + 1);
          int O         = yVal;
          double alpha  = (T / (1 + T)) * (xLength + yLength);
          double ubound = 0;
          if (px < py) {
            ubound = yVal + xLength - px;
            if (ubound > alpha) {
              std::tr1::unordered_map<int, int> xFeatures;
              int wID = 0;
              int df = 0;
              for (int i = px + 1; i < xLength; i++) {
                x.getFeature(i, wID, df);
                xFeatures.insert(std::make_pair<int, int>(wID, 1));
              }
              for (int i = yVal + 1; i < yLength; i++) {
                y.getFeature(i, wID, df);
                if ((xFeatures.find(wID)) != xFeatures.end()) {
                  O++;
                }
              }
            } else {
              //std::cout << ubound << " > " << alpha << std::endl;
            }
        } else {
            ubound = yVal + yLength - py;
            if (ubound > alpha) {
              std::tr1::unordered_map<int, int> xFeatures;
              int wID = 0;
              int df = 0;
              for (int i = yVal + 1; i < xLength; i++) {
                x.getFeature(i, wID, df);
                xFeatures.insert(std::make_pair<int, int>(wID, 1));
              }
              for (int i = py + 1; i < yLength; i++) {
                y.getFeature(i, wID, df);
                if ((xFeatures.find(wID)) != xFeatures.end()) O++;
              }
            } else {
              //std::cout << ubound << " > "  << alpha << std::endl;
            }
          }
          if (O >= alpha) {
            result.push_back(yID);
          }
        }
        itrA++;
      }
    }

    bool openDB(std::string& path)
    {
      bool rv = true;
      std::string dfPath = path + "df.hdb";
      dfHdb = tchdbnew();
      if(!tchdbopen(dfHdb, dfPath.c_str(), pocketj::Analyzer::TRUNC)) {
        rv = false;
      }

      std::string wordIdPath = path + "word_id.hdb";
      wordIdHdb = tchdbnew();
      if(!tchdbopen(wordIdHdb, wordIdPath.c_str(), pocketj::Analyzer::TRUNC)) {
        rv = false;
      }
      tchdbput2(wordIdHdb, pocketj::MAX_WORD_ID.c_str(), "0");

      return rv;
    }

    bool closeDB()
    {
      tchdbclose(wordIdHdb);
      tchdbdel(wordIdHdb);
      tchdbclose(dfHdb);
      tchdbdel(dfHdb);

      return true;
    }
  };
}
